import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution994 {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue=new LinkedList<>();
        int[][] visit=new int[grid.length][grid[0].length];
        for (int i=0;i<visit.length;i++){
            Arrays.fill(visit[i],-1);
        }
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==2){
                    queue.offer(new int[]{i,j});
                    visit[i][j]=0;
                }
            }
        }
        int[] dx=new int[]{1,0,-1,0};
        int[] dy=new int[]{0,1,0,-1};
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            for (int i=0;i<4;i++){
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]==1 && visit[x][y]==-1){
                    visit[x][y]=visit[t[0]][t[1]]+1;
                    queue.offer(new int[]{x,y});
                }
            }
        }
        int max=0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]==1){
                    if (visit[i][j]==-1){
                        return -1;
                    }
                    max=Math.max(max,visit[i][j]);
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new Solution994().orangesRotting(new int[][]{{2,1,1},{1,1,0},{0,1,1}}));
    }
}
